#include <bits/stdc++.h>
using namespace std;
int n, m;

int f[201];
int w[31], c[31];

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> c[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int v = w[i]; v <= m; v++) {
            f[v] = max(f[v], f[v - w[i]] + c[i]);
        }
    }

    cout << "max=" << f[m];
    return 0;
}